//
// Created by Administrator on 2021/5/11.
//
#include <string>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    int scoreOfParentheses(string S) {
        stack<int> ans;
        for (const auto &ch : S) {
            if (ch == ')' and !ans.empty()) { // 右括号
                if (ans.top() == -1) { // 栈顶是左括号
                    ans.pop();
                    pushNum(ans, 1);
                } else {  // 栈顶是数字 将其两倍入栈
                    int former = ans.top();
                    ans.pop();
                    ans.pop();
                    pushNum(ans, former * 2);
                }
            } else { // 左括号 用 -1 表示
                ans.push(-1);
            }
        }
        return ans.top();
    }

    void pushNum(stack<int> &ans, int num) { // 辅助函数 将一个数字入栈
        if (ans.empty()) ans.push(num);
        else {
            if (ans.top() != -1) { // 如果栈顶已经是一个数字，则将他们的和入栈
                int former = ans.top();
                ans.pop();
                ans.push(former + num);
            } else ans.push(num);  // 栈顶是'('，直接将数字入栈
        }
    }
};

class Solution2 { // 题解 分治
public:
    int scoreOfParentheses(string S) {
        return F(S, 0, S.size());
    }

    int F(string &S, int i, int j) {
        //Score of balanced string S[i:j]
        int ans = 0, bal = 0;
        // Split string into primitives
        for (int k = i; k < j; ++k) {
            bal += S[k] == '(' ? 1 : -1;
            if (bal == 0) {
                if (k - i == 1) ans++; // 得1分
                else ans += 2 * F(S, i + 1, k); // 继续拆分
                i = k + 1;
            }
        }
        return ans;

    }
};

class Solution3 { // 题解 栈
public:
    int scoreOfParentheses(string S) {
        stack<int> s;
        s.push(0);
        for (const auto &c:S) {
            if (c == '(')
                s.push(0);
            else {
                int v = s.top();
                s.pop();
                int w = s.top();
                s.pop();
                s.push(w + max(2 * v, 1));
            }
        }
        return s.top();
    }
};

class Solution4 { // 题解 栈
public:
    int scoreOfParentheses(string S) {
        int ans = 0, bal = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == '(') bal++;
            else {
                bal--;
                if (S[i - 1] == '(') {
                    ans += 1 << bal;  // 括号深度
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution4 sol;
    cout << sol.scoreOfParentheses("()") << endl;
    cout << sol.scoreOfParentheses("(())") << endl;
    cout << sol.scoreOfParentheses("()()") << endl;
    cout << sol.scoreOfParentheses("(()(()))") << endl;
    return 0;
}